
// enum - full enumeration of knapsack solutions

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

FILE *fp;

int N;
int C;
int *w;      // array of item weights
int *v;      // array of item values (or profits)
int *kindex;  // array of indexes to the items
int QUIET=0; // can be set to 1 to suppress output during enumeration

extern void read_knapsack_instance(char *filename);
extern void print_instance();
extern void sort_by_ratio();
extern int print_sol2(int *s,  int *tv, int *tw);
void enumerate();
int next_binary(int *str, int N);


int main(int argc, char *argv[])
{
  read_knapsack_instance(argv[1]);
  print_instance();
  enumerate();
  return(0);
}

void enumerate()
{
  int i=0;
  int x[N+1];   // binary vector representing items packed
  //int best_vector[N+1];  // binary vector for best solution found
  int best_value;
  double j=0;
  int tv, tw; // total value and total weight of current knapsack solution
  int f;

  int maxWeight=0;

  // set the knapsack initially empty
  for(i=1;i<=N;i++)
    x[i]=0;

  QUIET=1;  // change this to 1 to suppress output


  best_value=0;
  while(!(next_binary(&x[1], N)))
    {

      /* ADD CODE IN HERE TO KEEP TRACK OF FRACTION OF ENUMERATION DONE */
      int power = 0;
      double value = 0;
      for(int i=N; i>0; i--){
	value += x[i]*pow(2,power);
	power++;
      }
      double progress = (value/1048575)*100;
      printf("enumeration progress: %f %\n",progress);
      system("sh -c clear");
      
      f=print_sol2(x, &tv, &tw);  // calculates the value and weight and feasibility

      /* ADD CODE IN HERE TO KEEP TRACK OF BEST SOLUTION */
      if(f == 0){
      if(best_value<tv){
    	  best_value = tv;
      }
      if(maxWeight<tw){
    	  maxWeight = tw;
      }
      }

    }
    printf("the maximun value can be achieve is %d\n",best_value);
    printf("with the weight of %d\n",maxWeight);
}


int next_binary(int *str, int N)
{
  // Called with a binary string of length N, this
  // function adds "1" to the string, e.g. 0001 would turn to 0010.
  // If the string overflows, then the function returns 1, else it returns 0.
  int i=N-1;
  while(i>=0)
    {
      if(str[i]==1)
      {
	str[i]=0;
	i--;
      }
      else
      {
	str[i]=1;
	break;
      }
    }
  if(i==-1)
    return(1);
  else
    return(0);

}
